// 11.3 关联容器操作
/**
 * 除了表9.2（第295页）中列出的类型，关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。[插图]
 * 1. key_type     此容器类型的关键字类型
 * 2. mapped_type  每个关键字关联的类型，即值的类型，只适用于map
 * 3. value_type   对于set，与key_type相同；对于map，为pair<const key_type,mapped_type>
 * 与顺序容器一样（参见9.2.2节，第297页），我们使用作用域运算符来提取一个类型的成员——例如，map<string，int>：：key_type。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
using namespace std;

int main()
{
    // 11.3.5 访问元素
    // 对于允许重复关键字的容器，count还会做更多的工作：如果元素在容器中，它还会统计有多少个元素有相同的关键字。
    // 如果不需要计数，最好使用find：
    set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    iset.find(1);   // 返回一个迭代器，指向key==1的元素
    iset.find(11);  // 返回一个迭代器，其值等于iset.end()
    iset.count(1);  // 返回1
    iset.count(11); // 返回0
    // 在一个关联容器中查找元素的操作
    // lower_bound和upper_bound不适用于无序容器
    // 下标和at操作只适用于非const的map和unordered_map
    // c.lower_bound(k) 返回一个迭代器，指向第一个关键字不小于k的元素
    // c.upper_bound(k) 返回一个迭代器，指向第一个关键字大于k的元素
    // c.equal_range(k) 返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()

    // 对map使用find代替下标操作
    // 不能使用下标运算符来检查一个元素是否存在，因为如果关键字不存在的话，下标运算符会插入一个新元素。在这种情况下，应该使用find：[插图]
    map<string, size_t> word_count = {{"China", 1}, {"US", 2}, {"Japan", 3}};
    if (word_count.find("Australia") == word_count.end())
    {
        cout << "Australia is not int the map" << endl;
    }

    // 在multimap或multiset中查找元素
    // 如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。
    multimap<string, string> authors;
    authors.insert({"唐浩明", "曾国藩"}); // 插入第一个元素，关键字为唐浩明
    authors.insert({"唐浩明", "张之洞"}); // 插入第二个元素，关键字也为唐浩明
    authors.insert({"姚雪垠", "李自成"});
    string search_item("唐浩明");
    auto entries = authors.count(search_item); // 元素的数量
    auto iter = authors.find(search_item);     // 此作者第一本书
    while (entries)
    {
        cout << iter->second << endl; // 打印该作者的每本书
        ++iter;                       // 前进到下一本书
        --entries;                    //记录已经打印了多少本
    }

    // 如果关键字在容器中，lower_bound返回的迭代器将指向第一个具有给定关键字的元素，
    // 而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。
    // 如果元素不在multimap中，则lower_bound和upper_bound会返回相等的迭代器——指向一个不影响排序的关键字插入位置。
    for (auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); beg != end; ++beg)
    {
        cout << beg->second << endl; // 打印该作者的每本书
    }
    // 如果lower_bound和upper_bound返回相同的迭代器，则给定关键字不在容器中。

    // equal_range函数
    // 此函数接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，
    // 第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。
    for (auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first)
    {
        cout << pos.first->second << endl; // 打印该作者的每本书
    }
    // equal_range返回的pair。此pair的first成员保存的迭代器与lower_bound返回的迭代器是一样的，
    // second保存的迭代器与upper_bound的返回值是一样的。因此，在此程序中，pos.first等价于beg，pos.second等价于end。

    return 0;
}